package madixin.t112;

import javafx.util.Pair;

import java.util.Stack;

class Solution {

    /**
     * 迭代
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }

        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        stack.push(new Pair<>(root, sum));
        while (!stack.empty()) {
            Pair<TreeNode, Integer> curPair = stack.pop();
            TreeNode curNode = curPair.getKey();
            Integer curValue = curPair.getValue();
            if (curNode.left == null && curNode.right == null && curValue == curNode.val) {
                return true;
            }
            if (curNode.left != null) {
                stack.push(new Pair<>(curNode.left, curValue - curNode.val));
            }
            if (curNode.right != null) {
                stack.push(new Pair<>(curNode.right, curValue - curNode.val));
            }
        }
        return false;
    }

    /**
     * 递归
     */
    public boolean hasPathSum1(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        sum = sum - root.val;

        if (root.left == null && root.right == null && sum == 0) {
            return true;
        }

        return hasPathSum1(root.left, sum) || hasPathSum1(root.right, sum);
    }
}